#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N = 1e6+5,p = 6661;
int binom[p][p],S[p][p],mi[p],n,m;
int C(ll n,ll m)
{
    if(n < m||m < 0)return 0;
    if(n < p)return binom[n][m];
    return C(n/p,m/p)*C(n%p,m%p)%p;
}
int calc(ll n,ll m)
{return m<0?0:(calc(n/p,m/p-1)*mi[n%p]+C(n/p,m/p)*S[n%p][m%p])%p;}
struct node
{
    int l,r;ll v,vl;
    friend bool operator < (const node &x,const node &y){return x.l < y.l;}
};set<node> s;
auto split(int pos)
{
    auto it = --s.upper_bound({pos,0,0,0});
    node x = *it;if(x.l == pos)return it;
    s.erase(it);s.insert({x.l,pos-1,x.v,x.vl});
    return s.insert({pos,x.r,x.v,x.vl+pos-x.l}).first;
}
void assign(int l,int r,ll v)
{
    auto itr = split(r+1),itl = split(l);
    s.erase(itl,itr);s.insert({l,r,v,1});
}
inline int sum(ll n,ll l,ll r){return calc(n,r)-calc(n,l-1)+p;}
int query(int l,int r)
{
    int ans = 0;
    for(auto it = --s.upper_bound({l,0,0,0});;it++)
    {
        (ans += sum(it->v,max(l,it->l)-it->l+it->vl,min(r,it->r)-it->l+it->vl)) %= p;
        if(r <= it->r)break;
    }
    return ans;
}
char buf[1<<21],*p1,*p2;
inline ll rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    ll x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    freopen("izumi.in","r",stdin);
    freopen("izumi.out","w",stdout);
    for(int i = mi[0] = 1;i < p;i++)mi[i] = mi[i-1]*2%p;
    for(int i = 0;i < p;i++)
        for(int j = binom[i][0] = 1;j <= i;j++)
            binom[i][j] = (binom[i-1][j-1]+binom[i-1][j])%p;
    for(int i = 0;i < p;i++)for(int j = 0;j < p;j++)
        S[i][j] = ((j?S[i][j-1]:0)+binom[i][j])%p;
    n = rd();m = rd();s.insert({1,n,rd(),1});
    while(m--)
    {
        int op = rd(),l = rd(),r = rd();
        if(op == 1)assign(l,r,rd());
        else printf("%d\n",query(l,r));
    }
    return 0;
}